package solution.s_1365;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 解题思路：
 *      首先将 nums 进行排序。
 *      然后遍历排序后的数组，统计比当前数字小的数字个数，存入 Map 中。
 *      最后遍历初始的数组，从 Map 中取到对应的结果，返回。
 *
 *      统计比当前数字小的数字个数：
 *          比如，对于 [8,1,2,2,3]，首先进行排序，排序之后：[1,2,2,3,8]。
 *          对于 1 而言，它是第一个元素，所以比它大的元素个数为 0，此时发现 Map 中没有该元素，所以向 Map 中添加一个元素是 {1:0}；
 *          然后看第二个元素 2，它是第二个元素，所以比它大的元素个数为 1，Map 中没有该 key，向 Map 中插入元素 {2:1}；
 *          看第三个元素，发现 map 中已经有这个元素，那么跳过；
 *          ...
 *          直到整个列表结束。
 */
public class Solution20201026 {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        if (nums.length <= 1) { return nums; }

        // 排序
        int[] nums2 = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums2);

        // 计算对于每个元素小于它的元素个数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i ++) {
            int curNum = nums2[i];
            if (! map.containsKey(curNum)) {
                map.put(curNum, i);
            }
        }

        // 根据元素数值查询小于当前元素的元素个数
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i ++) {
            result[i] = map.get(nums[i]);
        }

        return result;
    }
}
